

In [3]:

    
def is_empty(xx):
    assert type(xx) is list, "Argument to 'is_empty' was not a list"
    return len(xx) == 0

def head(xx):
    assert type(xx) is list, "Argument to 'head' was not a list"
    return xx[0]

def tail(xx):
    assert type(xx) is list, "Argument to 'tail' was not a list"
    assert len(xx) > 0, "List was empty"
    return xx[1:]

def cons(x, xx):
    assert type(xx) is list, "Second argument to 'cons' was not a list"
    return [x] + xx

def is_atom(x):
    return type(x) in [int, float, bool, str]

def is_seq(x, y):
    assert type(x) is str, 'First argument to is_equal was not a str'
    assert type(y) is str, 'Second argument to is_equal was not a str'
    return x == y

def add1(x):
    assert type(x) is int
    return x + 1

def sub1(x):
    assert type(x) is int
    assert x > 0, "Argument to 'sub1' was zero (or negative)"
    return x - 1

def is_zero(x):
    assert type(x) is int
    return x == 0

def is_str(x):
    return type(x) == str

def is_num(x):
    return type(x) == int

s = [1,2]
s.insert(0,99)
print s

print cons(1, [4,5,6])
print type(1) is int,type(1.5) is float,type(True) is bool,type('gg') is str
print [is_atom(x) for x in [1,1.5,True,'gg']]
#print is_equal([1], [1])
print is_seq('a', 'a')
print is_seq('a', 'b')









    



[99, 1, 2]
[1, 4, 5, 6]
True True True True
[True, True, True, True]
True
False

What You Need to Know

Numbers: 0, 1, 2, 3, ... (i.e., no negative numbers or decimals)

Strings: '', 'a', 'b', ..., 'aa', 'ab', ...

Booleans: True, False

Lists: [], but you can make lists (see 'cons' below)

Functions

is_seq(x, y): x and y must both be strings; returns whether x equals y

is_empty(xx) : xx must be a list; returns whether the xx is the empty list

head(xx): xx must be a non-empty list; returns the first item

tail(xx): xx must be a non-empty list; returns a list with everything after the head

cons(h, tl): returns a list whose first item is h and whose remaining items are the items of tl (i.e. it put backs a list taken apart by head and tail)

add1(n): n must be a number; returns a number one bigger than n

sub1(n): n must be a number greater than zero; returns a number one less than n

is_zero(n): n must be a number; returns whether n is zero

is_str(x): returns whether x is a string

is_num(x): returns whether x is a number



In [4]:

    
is_seq('a', 'a')









    Out[4]:





True



In [5]:

    
is_seq('a', 'ab')









    Out[5]:





False



In [6]:

    
is_seq(42, 42)









    



---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-6-f17bf97f6fa2> in <module>()
----> 1 is_seq(42, 42)

<ipython-input-2-432750efb509> in is_seq(x, y)
     19 
     20 def is_seq(x, y):
---> 21     assert type(x) is str, 'First argument to is_equal was not a str'
     22     assert type(y) is str, 'Second argument to is_equal was not a str'
     23     return x == y

AssertionError: First argument to is_equal was not a str



In [7]:

    
is_empty([])









    Out[7]:





True



In [8]:

    
is_empty([1,2]) # not really allowed









    Out[8]:





False



In [9]:

    
is_empty(99)









    



---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-9-c6af935a014b> in <module>()
----> 1 is_empty(99)

<ipython-input-2-432750efb509> in is_empty(xx)
      1 def is_empty(xx):
----> 2     assert type(xx) is list, "Argument to 'is_empty' was not a list"
      3     return len(xx) == 0
      4 
      5 def head(xx):

AssertionError: Argument to 'is_empty' was not a list



In [10]:

    
head([1,2])









    Out[10]:





1



In [11]:

    
head([1])









    Out[11]:





1



In [12]:

    
head([])









    



---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-12-f30cd18eafcb> in <module>()
----> 1 head([])

<ipython-input-2-432750efb509> in head(xx)
      5 def head(xx):
      6     assert type(xx) is list, "Argument to 'head' was not a list"
----> 7     return xx[0]
      8 
      9 def tail(xx):

IndexError: list index out of range



In [13]:

    
tail([1,2,3])









    Out[13]:





[2, 3]



In [14]:

    
tail([1,2])









    Out[14]:





[2]



In [15]:

    
tail([1])









    Out[15]:





[]



In [18]:

    
tail([])









    



---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-18-0f45faf87aa7> in <module>()
----> 1 tail([])

<ipython-input-17-4e819dad5ed9> in tail(xx)
      9 def tail(xx):
     10     assert type(xx) is list, "Argument to 'tail' was not a list"
---> 11     assert len(xx) > 0, "List was empty"
     12     return xx[1:]
     13 

AssertionError: List was empty



In [20]:

    
cons(1, [2,3])









    Out[20]:





[1, 2, 3]



In [22]:

    
cons(1, [2])









    Out[22]:





[1, 2]



In [23]:

    
cons(1, [])









    Out[23]:





[1]



In [24]:

    
cons(1, cons(2, cons(3, [])))









    Out[24]:





[1, 2, 3]



In [27]:

    
add1(56)









    Out[27]:





57



In [28]:

    
add1(0)









    Out[28]:





1



In [29]:

    
sub1(100)









    Out[29]:





99



In [2]:

    
sub1(0)









    



---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-2-9178622a8b6f> in <module>()
----> 1 sub1(0)

<ipython-input-1-aaba59daf732> in sub1(x)
     30 def sub1(x):
     31     assert type(x) is int
---> 32     assert x > 0, "Argument to 'sub1' was zero (or negative)"
     33     return x - 1
     34 

AssertionError: Argument to 'sub1' was zero (or negative)



In [32]:

    
is_zero(9)









    Out[32]:





False



In [33]:

    
is_zero(0)









    Out[33]:





True



In [4]:

    
is_zero('kk')









    



---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-4-34e0831c86b4> in <module>()
----> 1 is_zero('kk')

<ipython-input-3-295cbe89fc18> in is_zero(x)
     34 
     35 def is_zero(x):
---> 36     assert type(x) is int
     37     return x == 0
     38 

AssertionError:



In [5]:

    
is_str('hello')









    Out[5]:





True



In [6]:

    
is_str(99)









    Out[6]:





False



In [8]:

    
is_str(['hello'])









    Out[8]:





False



In [9]:

    
is_num(9)









    Out[9]:





True



In [10]:

    
is_num('9')









    Out[10]:





False



In [11]:

    
is_num([99])









    Out[11]:





False



In [35]:

    
is_atom(9)









    Out[35]:





True



In [36]:

    
is_atom('bla')









    Out[36]:





True



In [37]:

    
is_atom([])









    Out[37]:





False



In [12]:

    
is_atom([89,90])









    Out[12]:





False



In [13]:

    
# is_lnums([1,2,3]) is True
# is_lnums([1,2,'ff']) is False
# is_lnums([]) is True
def is_lnums(xx):
    if is_empty(xx):
        return True
    else:
        # head(xx) and tail(xx)
        # is_num(head(xx))
        if is_num(head(xx)):
            return is_lnums(tail(xx))
        else:
            return False



In [14]:

    
is_lnums([1,2,3])









    Out[14]:





True



In [15]:

    
is_lnums([1,2,'a'])









    Out[15]:





False



In [16]:

    
is_lnums([])









    Out[16]:





True



In [17]:

    
# is_mem(x, l)
# is_mem('a', ['a', 'b']) is True
# is_mem('a', ['b']) is False
def is_str_mem(x, l):
    if is_empty(l):
        return False
    else:
        # head(l), tail(l)
        if is_seq(head(l), x):
            return True
        else:
            return is_str_mem(x, tail(l))



In [18]:

    
is_str_mem('a', ['a', 'b'])









    Out[18]:





True



In [19]:

    
is_str_mem('a', ['b', 'a'])









    Out[19]:





True



In [20]:

    
is_str_mem('a', ['b'])









    Out[20]:





False



In [25]:

    
# remove_str_mem('a', ['a', 'b', 'c']) gives ['b', 'c']
# remove_str_mem('a', ['b', 'c']) gives ['b', 'c']
# remove_str_mem('a', ['a', 'b', 'a']) gives ['b', 'a']
def remove_str_mem(x, l):
    if is_empty(l):
        return []
    else:
        # head(l), tail(l)
        if is_seq(x, head(l)):
            return tail(l)
        else:
            return cons(head(l), remove_str_mem(x, tail(l)))



In [26]:

    
remove_str_mem('a', ['a', 'b'])









    Out[26]:





['b']



In [27]:

    
remove_str_mem('a', ['b'])









    Out[27]:





['b']



In [28]:

    
remove_str_mem('a', ['b', 'a', 'c'])









    Out[28]:





['b', 'c']



In [29]:

    
remove_str_mem('a', ['a', 'a'])









    Out[29]:





['a']



In [ ]:



In [39]:

    
# Do we have a listof atoms?
# Example: [1,'a', 99] : yes
#          [1, []] : no

def is_lat(l):
    if is_empty(l):
        return True
    else:
        return is_atom(head(l)) and is_lat(tail(l))



In [40]:

    
is_lat([1,2,3])









    Out[40]:





True



In [41]:

    
is_lat([])









    Out[41]:





True



In [42]:

    
is_lat([1,2,[]])









    Out[42]:





False



In [44]:

    
# is_mem(x, l)
# is_mem('a', ['a', 'b']) is True
# is_mem('a', ['b'])

def is_mem(x, l):
    if is_empty(l):
        # do something
        # is_mem('a', [])
        return False
    else:
        # do something with head(l) and tail(l)
        # is_mem('a', ['a', 'b'])
        # head(l) is 'a'
        # tail(l) is ['b']
        if is_seq(x, head(l)):
            return True
        return is_mem(x, tail(l))



In [45]:

    
is_mem('a', ['a', 'b'])









    Out[45]:





True



In [46]:

    
is_mem('a', ['b', 'a'])









    Out[46]:





True



In [47]:

    
is_mem('a', ['b', 'c'])









    Out[47]:





False



In [54]:

    
# remove_member('a', ['a', 'b', 'c']) is ['b', 'c']
# remove_member('a', []) is []
# remove_member('a', ['a', 'b', 'a', 'c']) is ['b', 'a', 'c']

def remove_mem(x, l):
    if is_empty(l):
        return []
    else:
        if is_seq(head(l), x):
            return tail(l)
        else:
            return cons(head(l),remove_mem(x, tail(l)))



In [55]:

    
remove_mem('a', ['a', 'b', 'c'])









    Out[55]:





['b', 'c']



In [56]:

    
remove_mem('b', ['a', 'b', 'c'])









    Out[56]:





['a', 'c']



In [ ]:



In [29]:

    
def is_lat(xx):
    if is_empty(xx):
        return True
    elif is_atom(head(xx)):
        return is_lat(tail(xx))
    else:
        return False

print is_lat([])
print is_lat([1])
print is_lat([1, 2])
print is_lat([1, 2, []])









    



True
True
True
False



In [34]:

    
def is_member(x, lst):
    if is_empty(lst):
        return False
    else:
        return is_str_equal(x, head(lst)) or is_member(x, tail(lst))

print is_member('a', [])
print is_member('a', ['a'])
print is_member('a', ['b'])
print is_member('a', ['b', 'a'])









    



False
True
False
True



In [58]:

    
def remove_member(x, lst):
    if is_empty(lst):
        return []
    else:
        h = head(lst)
        tl = tail(lst)
        if is_seq(x, h):
            return tl
        else:
            return cons(h, remove_member(x, tl))
        
print remove_member('a', [])
print remove_member('a', ['a'])
print remove_member('a', ['b'])
print remove_member('a', ['a', 'x'])
print remove_member('a', ['a', 'x'])
print remove_member('a', ['x', 'a'])
print remove_member('a', ['a', 'x', 'a'])









    



[]
[]
['b']
['x']
['x']
['x']
['x', 'a']



In [31]:

    
# last([1,2,3]) is 3
# last([1,2]) is 2
# last([1]) is 1
# last([]) is error
def last(l):
    if is_empty(tail(l)):
        return head(l)
    else:
        return last(tail(l))



In [33]:

    
last([1,2,3])









    Out[33]:





3



In [35]:

    
last([])









    



---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-35-bee5c42f7665> in <module>()
----> 1 last([])

<ipython-input-31-13406cf6aac7> in last(l)
      4 # last([]) is error
      5 def last(l):
----> 6     if is_empty(tail(l)):
      7         return head(l)
      8     else:

<ipython-input-3-295cbe89fc18> in tail(xx)
      9 def tail(xx):
     10     assert type(xx) is list, "Argument to 'tail' was not a list"
---> 11     assert len(xx) > 0, "List was empty"
     12     return xx[1:]
     13 

AssertionError: List was empty



In [38]:

    
# firsts([[1,2], ['apple', 'pear', 'peach']]) is [1, 'apple']
# firsts([]) is []
# firsts([[99]]) is [99]
def firsts(l):
    if is_empty(l):
        return []
    else:
        return cons(head(head(l)), firsts(tail(l)))



In [39]:

    
firsts([[1,2], ['apple', 'pear', 'peach']])









    Out[39]:





[1, 'apple']



In [40]:

    
# add1_to_list([1,10,100]) = [2,11,101]
# add1_to_list([]) = []



In [59]:

    
def firsts(xx):
    if is_empty(xx):
        return []
    else:
        h = head(xx)
        tl = tail(xx)
        return cons(head(h), firsts(tl))



In [60]:

    
firsts([[1,2], [3,4]])









    Out[60]:





[1, 3]



In [62]:

    
def insert_right(x1, x2, xx):
    if is_empty(xx):
        return []
    else:
        h = head(xx)
        tl = tail(xx)
        if is_seq(h, x1):
            return cons(x1, cons(x2, tl))
        else:
            return cons(h, insert_right(x1, x2, tl))



In [64]:

    
insert_right('a', 'x', ['a', 'b', 'c'])









    Out[64]:





['a', 'x', 'b', 'c']



In [65]:

    
insert_right('a', 'x', ['a', 'b', 'c', 'a'])









    Out[65]:





['a', 'x', 'b', 'c', 'a']



In [ ]: